#include <cstdio>
#include <cstdlib>
#include <deque>
using std::deque;

using cmpst = std::pair<int, int>; // first: index; second: value

int n, k;
int a[1000001] = {0};
int _min[1000001] = {0};
int _max[1000001] = {0};

deque<cmpst> dq; // max = head; min = tail

void push_max(cmpst elem)
{
    while (dq.front().first < elem.first - k)
    {
        dq.pop_front();
    }
    if (dq.front().second < elem.second)
        dq.push_front(elem);
}

void push_min(cmpst elem)
{
    while (dq.front().first < elem.first - k)
    {
        dq.pop_back();
    }
    if (dq.back().second > elem.second)
        dq.push_back(elem);
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", a + i);
    }
    dq.push_back(std::make_pair(0, a[0]));
    for (int i = 1; i < k; ++i)
    {
        push_min(std::make_pair(i, a[i]));
        push_max(std::make_pair(i, a[i]));
    }
    for (int i = 0; i < n; ++i)
    {
        push_min(std::make_pair(i, a[i]));
        // _min[i] = a[i];
        push_max(std::make_pair(i, a[i]));
        // _max[i] = a[i];
        /* for (int j = 0; j < k; ++j)
        {
            _min[i] = (_min[i] > a[i + j]) ? a[i + j] : _min[i];
            _max[i] = (_max[i] < a[i + j]) ? a[i + j] : _max[i];
        } */
        _min[i] = dq.back().second;
        _max[i] = dq.front().second;
    }
    for (int i = 0; i < n - k + 1; ++i)
        printf("%d ", _min[i]);
    putchar('\n');
    for (int i = 0; i < n - k + 1; ++i)
        printf("%d ", _max[i]);
    putchar('\n');
    return 0;
}